Field of the Invention
This invention relates to digital maps of the type for displaying networks of roads and other features of geographical areas, and more specifically, toward a system and method for generating, extending, and revising networks of large geographical areas.
Related Art
Navigation systems, electronic or digital maps, and geographical positioning devices are increasingly used by travelers to assist with various navigation functions, such as to determine the overall position and orientation of the traveler and/or vehicle, find destinations and addresses, calculate optimal routes, and provide real-time driving guidance. Current navigation systems and devices include Personal Navigation Systems (PNAV), such as dedicated handheld navigation systems, Personal Digital Assistance (PDAs), mobile telephones provided with a navigation module, as well as in-car navigation systems and devices, such as those manufactured by TomTom N.V. (www.tomtom.com). Typically, the navigation system includes a small display screen or graphic user interface that portrays a network of streets as a series of line segments, and other features of a geographical area. The traveler can then be generally located on the digital map.
FIG. 1 shows a digital vector map of a road network, including major motorways, secondary roads, tertiary streets, and alleys. As will be appreciated by reference to these figures, in combination with the expense and effort required to produce digital maps, it may be the case that an existing roadway map or network is incomplete in its depiction of all roadways or paths within a given region. Furthermore, due to the evolving nature of networks which may include but are not limited to roadways and paths, changes may occur over time such that an existing digital map may no longer accurately portray current conditions. Thus, digital maps are often extended and new digital maps are occasionally generated.
Digital maps are expensive to generate, extend, and revise, since exhibiting and processing road information is very costly. Surveying methods or digitizing satellite images are commonly employed techniques for generating a digital map. One example of a non-incremental map generation process developed and currently used by TomTom N.V includes collecting a plurality of probe data over a period of time, providing the plurality probe data as a set of probe data to a processor, and processing the set of probe data to generate, extend, or revise a digital map. Probe traces are a plurality of sequential location measurements from location sensors housed in a plurality of vehicles or carried by a plurality of pedestrians. For example, the location sensors can be satellite navigation signal receivers, e.g. GPS systems.
However, for larger geographical areas, such as an entire country or world, the map generation systems and methods of the prior art are less efficient and reliable. The computation capacity of existing computers is not sufficient to generate digital maps in real-time when the system employs a single thread. One method currently used to generate road networks extending across large geographical areas is to divide the large geographical area into several tiles. Each of the tiles includes traces, and typically only portions of traces, extending across the tile. Each tile includes a single thread employing the trace or portion of the trace disposed in the single tile and generating a road segments limited to the single tile. The thread generates the road segments of the single tile independent of the other traces and independent of other portions of traces and traces disposed in other tiles. In other words, each thread employs the traces or portions of trace of only one of the tiles at a time to generate road segments of the tile independent of the other threads and other tiles. The threads can employ a map generation method to generate the independent road segments of the tile. Test results indicate the road segments generated in a single tile are relatively accurate.
However, to form a single road network of the entire large geographical area, the independent road segments of the individual tiles must be seamed together. Errors typically occur during the seaming step, when adjacent individual tiles are combined together. For example, the road segments of one tile may include two road segments disposed close to one another, whereas an adjacent tile includes only a single road segment. Thus, when the adjacent tiles are seamed together, the resulting road network of the large geographical area has an obvious error at the boundary between adjacent tiles. A second example error occurs when the geographic area includes a road disposed along or crossing a boundary between two adjacent tiles, and thus the probe data includes numerous traces extend across the adjacent tiles. When the tiles of the second example are seamed together, typically two road segments are generated, including one road segment in each adjacent tile, but in reality only one road segment exists. Similar errors occur at corners of adjacent tiles. Such errors typically occur with all types of network generation methods, both incremental and non-incremental, when attempting to generate a road network of a large geographical area. Examples of incremental map generation algorithms can be found in U.S. Pat. No. 6,385,539 and in the Applicant's co-pending PCT application titled “INCREMENTAL MAP GENERATION, REFINEMENT AND EXTENSION WITH GPS TRACES” by inventor H. Mund (PCT/EP2009/063938 filed 22 Oct. 2009).